import java.util.Stack;
import java.util.LinkedList;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(int x) {
        val = x;
    }

    public TreeNode() {}

    @Override
    public String toString() {
        return "[" + val + "]";
    }

    /* 前序遍历--递归的写法
    public static void preOrder(TreeNode tree) {
        if (tree == null)
            return;
        System.out.printf(tree.val + "");
        preOrder(tree.left);
        preOrder(tree.right);
    }
    */

    /** 前序遍历--非递归的写法 */
    public static void preOrder(TreeNode tree) {
        if (tree == null)
            return;
        Stack<TreeNode> q1 = new Stack<>();
        q1.push(tree); // 压栈
        while (!q1.empty()) {
            TreeNode t1 = q1.pop(); // 出栈
            System.out.println(t1.val);
            if (t1.right != null) {
                q1.push(t1.right);
            }
            if (t1.left != null) {
                q1.push(t1.left);
            }
        }
    }

    // 中序遍历--递归实现
    /*
    public static void inOrderTraversal(TreeNode node) {
        if (node == null)
            return;
        inOrderTraversal(node.left);
        System.out.println(node.val);
        inOrderTraversal(node.right);
    }
    */

    // 非递归实现
    public static void inOrderTraversal(TreeNode node) {
        if (node == null)
            return;
        Stack<TreeNode> stack = new Stack<>();
        
        while (node != null || !stack.empty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.println(node.val);
                node = node.right;
            }
        }
    }

    /*
    public static void postOrder(TreeNode node) {
        if (node == null)
            return;
        postOrder(node.left);
        postOrder(node.right);
    }
    */

    public static void postOrder(TreeNode node) {
        if (node == null)
            return;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(node);
        
        while (!s1.empty()) {
            node = s1.pop();
            s2.push(node);
            if (node.left != null) {
                s1.push(node.left);
            }
            if (node.right != null) {
                s1.push(node.right);
            }
        }

        while (!s2.empty()) {
            System.out.print(s2.pop().val + " ");
        }
    }

    // 层序遍历
    public static void levelOrder(TreeNode tree) {
        if (tree == null) 
            return;
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(tree);
    
        while (!list.isEmpty()) {
            TreeNode node = list.poll();
            System.out.println(node.val);
            if (node.left != null)
                list.add(node.left);
            if (node.right != null)
                list.add(node.right);
        }
    }

}